home *** CD-ROM | disk | FTP | other *** search
/ Gold Medal Software 1 / Gold Medal Software Volume 1 (Gold Medal) (1994).iso / prog / tpwprog3.arj / USEARCH.PAS < prev    next >
Encoding:
Pascal/Delphi Source File  |  1992-07-02  |  6.3 KB  |  159 lines
  1. {******************************************************************}
  2. {                                                                  }
  3. {     Mancala                                                      }
  4. {     Turbo Pascal for Windows                                     }
  5. {     Copyright (c) 1991 by Swan Software. All rights reserved.    }
  6. {                                                                  }
  7. {******************************************************************}
  8.  
  9. { usearch.pas -- Alpha/Beta game search engine for Mancala }
  10.  
  11. unit USearch;
  12.  
  13. interface
  14.  
  15. uses WinTypes, WinProcs, UGlobals, UEval, UMove;
  16.  
  17. procedure Search(var Position: Boardrec; Level: Integer;
  18.   var FinalScore: Integer; MoveList: ListRec; Alpha: Integer;
  19.   Beta: Integer);
  20.  
  21.  
  22. implementation
  23.  
  24.  
  25. {- Perform minimax search with alpha-beta cutoffs. Finds best move
  26. that limits opponent's maximum potential gain. When finished, global
  27. bestmove equals the selected move. Requires variable MaxPly set to
  28. the maximum search depth. Start search with Level = 1. Variable
  29. FinalScore does not have to be initialized. MoveList.FirstIndex
  30. should address the list of legal moves (returned by MoveGen) for this
  31. level. Initialize Alpha to -maxInt and Beta to +Maxint when calling
  32. search the first time. If there are no moves for this position
  33. (MoveList.Count = 0), the FinalScore is the board evaluation. When this
  34. procedure ends, the global MoveStack index (MoveIndex) is reset to
  35. MoveLst.FirstIndex - 1, removing the MoveList from the stack and
  36. recovering the space the moves occupy. After this procedure ends,
  37. then, MoveList is no longer valid. Set global LowLevel to the level
  38. used to start the search. If Level = 0, then the computer will search
  39. for human's best move. }
  40.  
  41. procedure Search(var Position: Boardrec; Level: Integer;
  42.   var FinalScore: Integer; MoveList: ListRec; Alpha: Integer;
  43.   Beta: Integer);
  44. var
  45.   M: Integer;               { Movestack index to MoveRecs }
  46.   NewList: ListRec;         { New move lists to search }
  47.   MinMaxIndex: StackRange;  { Index to MinMax move }
  48.   MaxScore: Integer;        { Max score on odd levels }
  49.   MinScore: Integer;        { Min score on even levels }
  50.   OldCursor: HCursor;       { Saved cursor handle during search }
  51. begin
  52.  
  53.   OldCursor := SetCursor(LoadCursor(0, idc_Wait));
  54.  
  55.   with MoveList do     { Investigate moves on this list }
  56.  
  57. {- If the MoveList is empty (Count = 0), then end the search now,
  58. leaving FinalScore unchanged. }
  59.  
  60.     if Count > 0 then
  61.     begin
  62.  
  63.       MinMaxIndex := FirstIndex;   { Initialize final move index
  64.                                      to the first move on the
  65.                                      sorted move list. }
  66.  
  67. {- Check the level. If it is less than the maximum ply number
  68. (MaxPly), then continue the search by calling MoveGen with the board
  69. position reached after making each move on the move list. If the
  70. search level equals MaxPly, then the search has reached the deepest
  71. level of the tree and MinMaxIndex equals the MoveStack index of the
  72. chosen move on this level. }
  73.  
  74.       if Level < MaxPly then
  75.       begin  { Continue searching for the best move }
  76.         M := FirstIndex;           { Initialize move index }
  77.         MaxScore := -maxInt;       { < any possible score }
  78.         MinScore := +maxInt;       { > any possible score }
  79.         while M <= LastIndex do with MoveStack[M] do
  80.         begin
  81.           with BoardStack[BoardIndex] do
  82.             if GoAgain then
  83.             begin
  84.               MoveGen(BoardStack[BoardIndex], Level, NewList);
  85.               Search(BoardStack[BoardIndex], Level, Score,
  86.                 NewList, Alpha, Beta);
  87.             end else
  88.             begin
  89.               MoveGen(BoardStack[BoardIndex], Level + 1, NewList);
  90.               Search(BoardStack[BoardIndex], Level + 1, Score,
  91.                 Newlist, Alpha, Beta);
  92.             end;
  93.  
  94. {- Keep track of greatest (Alpha) or lowest (Beta) score on this level
  95. for passing to further searches. The result, Alpha or Beta, also
  96. becomes the result of the minimax algorithm--the value passed up
  97. through the tree as the final score for this level. Odd levels affect
  98. alpha values, but use beta values to produce cutoffs. Even levels
  99. affect beta values but use alpha values for cutoffs. In this way, the
  100. alpha beta values double as variables holding the best or worst
  101. scores, while indicating from lower tree levels when there is no
  102. reason to continue searching. }
  103.  
  104.           if Odd(Level) then
  105.           begin
  106.             if Score > Alpha then       { Adjust alpha value }
  107.               Alpha := Score;
  108.             if Score > MaxScore then    { Record highest score }
  109.             begin
  110.               MaxScore := Score;        { Highest score so far }
  111.               MinMaxIndex := M;         { Movestack index }
  112.             end;
  113.             if Score >= Beta then
  114.               M := LastIndex;           { Beta cutoff }
  115.           end else
  116.           begin
  117.             if Score < Beta then        { Adjust beta value }
  118.               Beta := Score;
  119.             if Score < MinScore then    { Record lowest score }
  120.             begin
  121.               MinScore := Score;        { Lowest score so far }
  122.               MinMaxIndex := M;         { MoveStack index }
  123.             end;
  124.             if Score <= Alpha then
  125.               M := LastIndex;           { Alpha cutoff }
  126.           end;
  127.           Inc(M);                       { Advance move index }
  128.         end;
  129.       end;
  130.  
  131.       with MoveStack[MinMaxIndex] do    { Select minimax move }
  132.       begin
  133.         FinalScore := Score;            { Pass up final score }
  134.         BestMove := Move;               { Assign best move }
  135.       end;
  136.  
  137. {- Setting the global MoveIndex to FirstIndex - 1 moves the index
  138. back to its position before the move list for this search level was
  139. generated. The MoveIndex is the stack pointer to the MoveStack and
  140. BoardStack arrays. This action, then, reclaims space on the stack for
  141. future move lists and board copies. }
  142.  
  143.       MoveIndex := FirstIndex - 1;      { Dispose move list and
  144.                                           gameboard copies. }
  145.     end;
  146.  
  147.   SetCursor(OldCursor);
  148.  
  149. end;
  150.  
  151.  
  152. end.
  153.  
  154.  
  155. { ----------------------------------------------------------------
  156.   Copyright (c) 1991 by Swan Software. All rights reserved.
  157.   Revision 1.00    Date: 8/21/1991
  158.   ---------------------------------------------------------------- }
  159.